{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Increasing Decreasing String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #上升下降字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，请你根据下面的算法重新构造字符串：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>从 <code>s</code>&nbsp;中选出 <strong>最小</strong>&nbsp;的字符，将它 <strong>接在</strong>&nbsp;结果字符串的后面。</li>\n",
    "\t<li>从 <code>s</code>&nbsp;剩余字符中选出&nbsp;<strong>最小</strong>&nbsp;的字符，且该字符比上一个添加的字符大，将它 <strong>接在</strong>&nbsp;结果字符串后面。</li>\n",
    "\t<li>重复步骤 2 ，直到你没法从 <code>s</code>&nbsp;中选择字符。</li>\n",
    "\t<li>从 <code>s</code>&nbsp;中选出 <strong>最大</strong>&nbsp;的字符，将它 <strong>接在</strong>&nbsp;结果字符串的后面。</li>\n",
    "\t<li>从 <code>s</code>&nbsp;剩余字符中选出&nbsp;<strong>最大</strong>&nbsp;的字符，且该字符比上一个添加的字符小，将它 <strong>接在</strong>&nbsp;结果字符串后面。</li>\n",
    "\t<li>重复步骤 5&nbsp;，直到你没法从 <code>s</code>&nbsp;中选择字符。</li>\n",
    "\t<li>重复步骤 1 到 6 ，直到 <code>s</code>&nbsp;中所有字符都已经被选过。</li>\n",
    "</ol>\n",
    "\n",
    "<p>在任何一步中，如果最小或者最大字符不止一个&nbsp;，你可以选择其中任意一个，并将其添加到结果字符串。</p>\n",
    "\n",
    "<p>请你返回将&nbsp;<code>s</code>&nbsp;中字符重新排序后的 <strong>结果字符串</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aaaabbbbcccc&quot;\n",
    "<strong>输出：</strong>&quot;abccbaabccba&quot;\n",
    "<strong>解释：</strong>第一轮的步骤 1，2，3 后，结果字符串为 result = &quot;abc&quot;\n",
    "第一轮的步骤 4，5，6 后，结果字符串为 result = &quot;abccba&quot;\n",
    "第一轮结束，现在 s = &quot;aabbcc&quot; ，我们再次回到步骤 1\n",
    "第二轮的步骤 1，2，3 后，结果字符串为 result = &quot;abccbaabc&quot;\n",
    "第二轮的步骤 4，5，6 后，结果字符串为 result = &quot;abccbaabccba&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;rat&quot;\n",
    "<strong>输出：</strong>&quot;art&quot;\n",
    "<strong>解释：</strong>单词 &quot;rat&quot; 在上述算法重排序以后变成 &quot;art&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;leetcode&quot;\n",
    "<strong>输出：</strong>&quot;cdelotee&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;ggggggg&quot;\n",
    "<strong>输出：</strong>&quot;ggggggg&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;spo&quot;\n",
    "<strong>输出：</strong>&quot;ops&quot;\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 500</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [increasing-decreasing-string](https://leetcode.cn/problems/increasing-decreasing-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [increasing-decreasing-string](https://leetcode.cn/problems/increasing-decreasing-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aaaabbbbcccc\"', '\"rat\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        dic = [0]*26\n",
    "        for i in s:\n",
    "            dic[ord(i) - 97] += 1\n",
    "        while len(ans) < len(s):\n",
    "            for i in range(26):\n",
    "                if dic[i] != 0 :\n",
    "                    ans.append(chr(i+97))\n",
    "                    dic[i] -= 1\n",
    "            for i in range(25,-1,-1):\n",
    "                if dic[i] != 0 :\n",
    "                    ans.append(chr(i+97))\n",
    "                    dic[i] -= 1\n",
    "        res = ''.join(ans)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList as SL\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        sl = SL(s)\n",
    "        ans = \"\"\n",
    "        while sl:\n",
    "            # 从小到大\n",
    "            ans += sl.pop(0)\n",
    "            while 1:\n",
    "                try:\n",
    "                    ans += sl.pop(sl.bisect_right(ans[-1]))\n",
    "                except:\n",
    "                    break\n",
    "            # 从大到小\n",
    "            if sl:\n",
    "                ans += sl.pop(-1)\n",
    "                while 1:\n",
    "                    try:\n",
    "                        pos = sl.bisect_left(ans[-1]) - 1\n",
    "                        if pos < 0:\n",
    "                            break\n",
    "                        ans += sl.pop(pos)\n",
    "                    except:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        char_count = Counter(s)\n",
    "        result = ''\n",
    "        count = 0\n",
    "        while char_count:\n",
    "            key_list = sorted(list(char_count.keys()), reverse=False if count % 2 == 0 else True)\n",
    "            for key in key_list:\n",
    "                char_count[key] -= 1\n",
    "                result += key\n",
    "                if char_count[key] == 0:\n",
    "                    del char_count[key]\n",
    "            count += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        s_sort = sorted(list(set(s)))\n",
    "        s_reverse = sorted(list(set(s)),reverse=True)\n",
    "        res = ''\n",
    "        while True:\n",
    "            for ch in s_sort:\n",
    "                if s and ch in s:\n",
    "                    s = s.replace(ch,'',1)\n",
    "                    res += ch\n",
    "                elif s and ch not in s:\n",
    "                    continue\n",
    "                else:\n",
    "                    return res\n",
    "            for ch in s_reverse:\n",
    "                if s and ch in s:\n",
    "                    s = s.replace(ch, '', 1)\n",
    "                    res += ch\n",
    "                elif s and ch not in s:\n",
    "                    continue\n",
    "                else:\n",
    "                    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        str_counter = collections.Counter(s)\n",
    "        result = []\n",
    "        flag = False\n",
    "        while str_counter:\n",
    "            keys = list(str_counter.keys())\n",
    "            keys.sort(reverse=flag)\n",
    "            flag= not flag\n",
    "            result.append(''.join(keys))\n",
    "            str_counter-=collections.Counter(keys)\n",
    "        return ''.join(result)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def sortString(self, s: str) -> str:\n",
    "        num = [0] * 26\n",
    "        for ch in s:\n",
    "            num[ord(ch) - ord('a')] += 1\n",
    "        \n",
    "        ret = list()\n",
    "        while len(ret) < len(s):\n",
    "            for i in range(26):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "            for i in range(25, -1, -1):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "\n",
    "        return \"\".join(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        s_sort = sorted(list(set(s)))\n",
    "        s_reverse = sorted(list(set(s)),reverse=True)\n",
    "        res = ''\n",
    "        while True:\n",
    "            for ch in s_sort:\n",
    "                if s and ch in s:\n",
    "                    s = s.replace(ch,'',1)\n",
    "                    res += ch\n",
    "                elif s and ch not in s:\n",
    "                    continue\n",
    "                else:\n",
    "                    return res\n",
    "            for ch in s_reverse:\n",
    "                if s and ch in s:\n",
    "                    s = s.replace(ch, '', 1)\n",
    "                    res += ch\n",
    "                elif s and ch not in s:\n",
    "                    continue\n",
    "                else:\n",
    "                    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        c = dict(Counter(s))\n",
    "        li = sorted(c)\n",
    "        l , ans = len(s), \"\"\n",
    "        while l > 0:\n",
    "            for x in li:\n",
    "                if c[x] and l:\n",
    "                    ans += x\n",
    "                    c[x] -= 1\n",
    "                    l -= 1\n",
    "            for x in li[::-1]:\n",
    "                if c[x] and l:\n",
    "                    ans += x\n",
    "                    c[x] -= 1\n",
    "                    l -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        s_sort = sorted(list(set(s)))\n",
    "        s_reverse = sorted(list(set(s)),reverse=True)\n",
    "        res = ''\n",
    "        while True:\n",
    "            for ch in s_sort:\n",
    "                if s and ch in s:\n",
    "                    s = s.replace(ch,'',1)\n",
    "                    res += ch\n",
    "                elif s and ch not in s:\n",
    "                    continue\n",
    "                else:\n",
    "                    return res\n",
    "            for ch in s_reverse:\n",
    "                if s and ch in s:\n",
    "                    s = s.replace(ch, '', 1)\n",
    "                    res += ch\n",
    "                elif s and ch not in s:\n",
    "                    continue\n",
    "                else:\n",
    "                    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        a_ord, result, syllabus = ord('a'), \"\",  [0] * 26\n",
    "        word_q = []\n",
    "        for c in s:\n",
    "            c_ord = ord(c)\n",
    "            if syllabus[c_ord-a_ord] == 0:\n",
    "                word_q.append(c_ord-a_ord)\n",
    "            syllabus[c_ord-a_ord] += 1\n",
    "        word_q = sorted(word_q)\n",
    "        min_mode = True\n",
    "        while word_q:\n",
    "            i = 0 if min_mode else len(word_q)-1\n",
    "            while word_q and (min_mode and i < len(word_q) or not min_mode and i > -1):\n",
    "                syllabus[word_q[i]] -= 1\n",
    "                result += chr(word_q[i] + a_ord)\n",
    "                if syllabus[word_q[i]] > 0:\n",
    "                    i = i + (1 if min_mode else -1)\n",
    "                else:\n",
    "                    del word_q[i]\n",
    "                    if not min_mode: i -= 1\n",
    "            min_mode = not min_mode\n",
    "        return result\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        num = [0]*26\n",
    "        for ch in s:\n",
    "            num[ord(ch)-ord('a')] += 1\n",
    "\n",
    "        ret = list()\n",
    "        while len(ret) < len(s):\n",
    "            for i in range(26):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i+ord('a')))\n",
    "                    num[i] -= 1\n",
    "            for i in range(25,-1,-1):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i+ord('a')))\n",
    "                    num[i] -= 1\n",
    "        return \"\".join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        str_counter = collections.Counter(s)\n",
    "        result = []\n",
    "        flag = False\n",
    "        while str_counter:\n",
    "            keys = list(str_counter.keys())\n",
    "            keys.sort(reverse=flag)\n",
    "            flag = not flag\n",
    "            result.append(''.join(keys))\n",
    "            str_counter -= collections.Counter(keys)\n",
    "        return ''.join(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        cnt = [0]*26\n",
    "        for v in s:\n",
    "            cnt[ord(v)-ord('a')]+=1\n",
    "        \n",
    "\n",
    "        res = list()\n",
    "        while len(res) < len(s):\n",
    "            for i in range(26):\n",
    "                if cnt[i]:\n",
    "                    res.append(chr(i+ord('a')))\n",
    "                    cnt[i] -=1\n",
    "            for i in range(25, -1, -1):\n",
    "                if cnt[i]:\n",
    "                    res.append(chr(i+ord('a')))\n",
    "                    cnt[i]-=1\n",
    "     \n",
    "\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        a=''\n",
    "        while s!='':\n",
    "            b=sorted(list(set(s)))\n",
    "            for i in b:\n",
    "                a+=i\n",
    "                s=s.replace(i,'',1)\n",
    "            if s=='':break\n",
    "            b=sorted(list(set(s)))\n",
    "            for i in b[::-1]:\n",
    "                a+=i\n",
    "                s=s.replace(i,'',1)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        t = sorted(list(set(s)))\n",
    "        dic = Counter(s)\n",
    "        ans = \"\"\n",
    "        while True:\n",
    "            for c in t:\n",
    "                if dic[c] > 0:\n",
    "                    ans += c\n",
    "                    dic[c] -= 1\n",
    "            for c in t[::-1]:\n",
    "                if dic[c] > 0:\n",
    "                    ans += c\n",
    "                    dic[c] -= 1\n",
    "\n",
    "            if all(dic[c] == 0 for c in t):\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        ####使用数组存储字符出现的次数，然后模拟\n",
    "        tmp = [0] * 26\n",
    "        for i in s:\n",
    "            tmp[ord(i) - ord('a')] += 1\n",
    "        res = \"\"\n",
    "        n = len(s)\n",
    "        while len(res) < n:\n",
    "            index = 0\n",
    "            while index < 26:\n",
    "                if tmp[index] > 0:\n",
    "                    res += chr(index + ord('a'))\n",
    "                    if len(res) == n:\n",
    "                        return res\n",
    "                    tmp[index] -= 1\n",
    "                index += 1\n",
    "            index = 25\n",
    "            while index > -1:\n",
    "                if tmp[index] > 0:\n",
    "                    res += chr(index + ord('a'))\n",
    "                    if len(res) == n:\n",
    "                        return res\n",
    "                    tmp[index] -= 1\n",
    "                index -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        # c = Counter(s)\n",
    "        # n = len(s)\n",
    "        # res = ''\n",
    "        # d = 1\n",
    "        # i = 0\n",
    "        # chs = sorted(c.keys())\n",
    "        # while len(res) < n:\n",
    "        #     print(i)\n",
    "        #     if c[chs[i]]:\n",
    "        #         res += chs[i]\n",
    "        #         c[chs[i]] -= 1\n",
    "        #     if (i == 0 and d == -1) or (i == len(chs)-1 and d == 1):\n",
    "        #         d = -d\n",
    "        #     else:\n",
    "        #         i += d\n",
    "        # return res \n",
    "\n",
    "        # ---------------------------------\n",
    "        c = Counter(s)\n",
    "        res = ''\n",
    "        flag = False \n",
    "        while c:\n",
    "            keys = sorted(list(c.keys()), reverse=flag)\n",
    "            flag = not flag\n",
    "            res += ''.join(keys)\n",
    "            c -= Counter(keys)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        res=\"\"\n",
    "        st=[0]*26\n",
    "        n=len(s)\n",
    "        for c in s:\n",
    "            st[ord(c)-ord('a')]+=1\n",
    "        while len(res)!=n:\n",
    "            '''\n",
    "            s 中字符按照字母大小保存成列表。\n",
    "            从索引 0 遍历列表，如果索引上的值大于 0，就按顺序加到 res 后面，列表对应值 -1。\n",
    "            第二轮，从索引 n-1倒序遍历列表，只要索引上的值大于0，就加到 res 后面，列表对应值-1\n",
    "            '''\n",
    "            # 从索引 0 遍历列表，目的是从小到大顺序找字符\n",
    "            for i in range(26):\n",
    "                # 如果索引上的值大于 0，就表示这个字符存在。\n",
    "                if st[i]>0:\n",
    "                    # 转成字符，把字符加到 res 后面\n",
    "                    ch=chr(i+97)\n",
    "                    res+=ch\n",
    "                    # 列表元素-1\n",
    "                    st[i]-=1\n",
    "            # 从索引 n-1倒序遍历列表，目的是从大到小查找字符\n",
    "            for i in range(25,-1,-1):\n",
    "                if st[i]>0:\n",
    "                    # 转成字符\n",
    "                    ch=chr(i+97)\n",
    "                    res+=ch\n",
    "                    st[i]-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        num = [0] * 26\n",
    "        for ch in s:\n",
    "            num[ord(ch) - ord('a')] += 1\n",
    "        \n",
    "        ret = list()\n",
    "        while len(ret) < len(s):\n",
    "            for i in range(26):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "            for i in range(25, -1, -1):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "\n",
    "        return \"\".join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        ans = []\n",
    "        rev = False\n",
    "        while c:\n",
    "            # 第一遍从小到大\n",
    "            for char in sorted(c, reverse = rev):\n",
    "                ans.append(char)\n",
    "                c[char] -= 1\n",
    "            c = +c  # 清除计数为0的字母\n",
    "            rev = not rev   # 反转\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "LOWER = Counter(ascii_lowercase)\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        ans = []\n",
    "        rev = False\n",
    "        while c:\n",
    "            # 第一遍从小到大\n",
    "            l = sorted(c, reverse = rev)\n",
    "            ans.append(''.join(l))\n",
    "            c -= LOWER\n",
    "            rev = not rev   # 反转\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        seq = sorted(set(s)) # 建立s的不重复字符，并从小到大排序\n",
    "        rev = seq[::-1] # 切片反转seq，得到逆向的，从大到小排序\n",
    "        d = Counter(s) # 对s做统计，形成字典\n",
    "        max_value = 0 # 准备记录字典d最大value值\n",
    "        for key in d.keys():\n",
    "            if d[key]>max_value:max_value=d[key] #遍历字典d,获取最大value，为取字符的循环次数做准备\n",
    "\n",
    "        res = ''  \n",
    "        for n in range(max_value//2+1):  #取字符的循环次数，每次循环正向、逆向都执行1次\n",
    "            for k in range(len(d)): # 按从小到大顺序，每种字符取1个\n",
    "                if d[seq[k]]>0:  # 判断每种字符的数量\n",
    "                    res = res+seq[k] #该种字符数量还有，取1个加到结果res上\n",
    "                    d[seq[k]] -=1 # 该种字符的数量减1\n",
    "            for k in range(len(d)): # 同上循环，按逆向，即从大到小顺序，每种字符取1个\n",
    "                if d[rev[k]]>0:\n",
    "                    res = res+rev[k]\n",
    "                    d[rev[k]] -=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        ans = []\n",
    "        rev = False\n",
    "        while c:\n",
    "            l = sorted(c, reverse=rev)\n",
    "            ans.append(''.join(l))\n",
    "            c -= Counter(l)\n",
    "            rev = not rev\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        num = [0] * 26\n",
    "        for ch in s:\n",
    "            num[ord(ch) - ord('a')] += 1\n",
    "        \n",
    "        ret = list()\n",
    "        while len(ret) < len(s):\n",
    "            for i in range(26):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "            for i in range(25, -1, -1):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "\n",
    "        return \"\".join(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        record = collections.defaultdict(int)\n",
    "        for c in s:\n",
    "            record[c] += 1\n",
    "        temp = sorted(record.keys())\n",
    "        res = ''\n",
    "        flag = 1\n",
    "        while any(record[key] != 0 for key in record):\n",
    "            if flag % 2 == 1:\n",
    "                for key in temp:\n",
    "                    if record[key] > 0:\n",
    "                        res += key\n",
    "                        record[key] -= 1\n",
    "            else:\n",
    "                for key in temp[::-1]:\n",
    "                    if record[key] > 0:\n",
    "                        res += key\n",
    "                        record[key] -= 1\n",
    "            flag += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        str_counter = collections.Counter(s)\n",
    "        result = []\n",
    "        flag = False\n",
    "        while str_counter:\n",
    "            keys = list(str_counter.keys())\n",
    "            keys.sort(reverse=flag)\n",
    "            flag = not flag\n",
    "            result.append(''.join(keys))\n",
    "            str_counter -= collections.Counter(keys)\n",
    "        return ''.join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        h = [0] * 26\n",
    "        for i in s:\n",
    "            a = ord(i) - ord('a')\n",
    "            h[a] += 1\n",
    "        n = len(s)\n",
    "        res = ''\n",
    "        while n > 0:\n",
    "            for i in range(26):\n",
    "                if h[i] > 0:\n",
    "                    n -= 1\n",
    "                    h[i] -= 1\n",
    "                    res += chr(i + ord('a'))\n",
    "            for i in range(25,-1,-1):\n",
    "                if h[i] > 0:\n",
    "                    n -= 1\n",
    "                    h[i] -= 1\n",
    "                    res += chr(i + ord('a'))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "\n",
    "        ss = Counter(sorted(s))\n",
    "        result = \"\"\n",
    "\n",
    "        def test(ss, result, flag):\n",
    "            res = \"\"\n",
    "            for item in ss:\n",
    "                if ss[item] > 0:\n",
    "                    res += item\n",
    "                    ss[item] -= 1\n",
    "                else:\n",
    "                    continue\n",
    "            if len(res) == 0:\n",
    "                return result\n",
    "\n",
    "            if flag:\n",
    "                result += res\n",
    "                result = test(ss, result, False)\n",
    "            else:\n",
    "                result += res[::-1]\n",
    "                result = test(ss, result, True)\n",
    "            return result\n",
    "    \n",
    "        return test(ss,result, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        ds = Counter(sorted(s))\n",
    "        ans = ''\n",
    "        while len(ans) < len(s):\n",
    "            for k in ds.keys():\n",
    "                if ds[k]:\n",
    "                    ans += k \n",
    "                    ds[k] -= 1\n",
    "            for k in reversed(ds.keys()):\n",
    "                if ds[k]:\n",
    "                    ans += k \n",
    "                    ds[k] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "\n",
    "        def jiexiao(result,s):\n",
    "            ss = sorted(list(set([i for i in s])))\n",
    "            for i in ss:\n",
    "                s = s.replace(i,\"\",1)\n",
    "            result += \"\".join(ss)\n",
    "            \n",
    "            ss = sorted(list(set([i for i in s])),reverse = True)\n",
    "            for i in ss:\n",
    "                s = s.replace(i,\"\",1)\n",
    "            result += \"\".join(ss)\n",
    "            return result,s\n",
    "\n",
    "        result = \"\"\n",
    "        while len(s) != 0:\n",
    "            result,s = jiexiao(result,s)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        nums = [0]*26\n",
    "        for ch in s:\n",
    "            nums[ord(ch)-ord('a')] += 1\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        while len(ans) < n:\n",
    "            for i in range(26):\n",
    "                if nums[i]:\n",
    "                    ans.append(chr(ord('a')+i))\n",
    "                    nums[i] -= 1\n",
    "            for i in range(25,-1,-1):\n",
    "                if nums[i]:\n",
    "                    ans.append(chr(ord('a')+i))\n",
    "                    nums[i] -= 1\n",
    "        return ''.join(ans)   \n",
    "        '''\n",
    "        s=list(s)\n",
    "        s.sort()\n",
    "        ans = []\n",
    "        stack = []\n",
    "        ans.append(s[0])\n",
    "        n = len(s)\n",
    "        #print(s,ans)\n",
    "        for i in range(1,n):\n",
    "            if s[i] > ans[-1]:\n",
    "                ans.append(s[i])\n",
    "            else:\n",
    "                stack.append(s[i])\n",
    "            #print(stack,ans)\n",
    "        reverse = 1\n",
    "        while stack:\n",
    "            tmp = []\n",
    "            n = len(stack)\n",
    "            ans.append(stack[-1])\n",
    "            for i in range(n-2,-1,-1):\n",
    "                if reverse:\n",
    "                    if stack[i] < ans[-1]:\n",
    "                        ans.append(stack[i])\n",
    "                    else:\n",
    "                        tmp.append(stack[i])\n",
    "                else:\n",
    "                    if stack[i] > ans[-1]:\n",
    "                        ans.append(stack[i])\n",
    "                    else:\n",
    "                        tmp.append(stack[i])\n",
    "            stack = tmp\n",
    "            if reverse == 1:\n",
    "                reverse = 0\n",
    "            else:\n",
    "                reverse = 1\n",
    "        return ''.join(ans)\n",
    "        '''\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        h = [0] * 26\n",
    "        for i in s:\n",
    "            a = ord(i) - ord('a')\n",
    "            h[a] += 1\n",
    "        n = len(s)\n",
    "        res = ''\n",
    "        def add_letter(x):\n",
    "            nonlocal n,res\n",
    "            if h[i] > 0:\n",
    "                n -= 1\n",
    "                h[i] -= 1\n",
    "                res += chr(i + ord('a'))\n",
    "        while n > 0:\n",
    "            for i in range(26):\n",
    "                add_letter(i)\n",
    "            for i in range(25,-1,-1):\n",
    "                add_letter(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        s = sorted(s)\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        while n:\n",
    "            mi = ''\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == '':\n",
    "                    continue\n",
    "                if not mi:\n",
    "                    mi = s[i]\n",
    "                    res.append(s[i])\n",
    "                    s[i] = ''\n",
    "                    n -= 1\n",
    "                else:\n",
    "                    if mi != s[i]:\n",
    "                        res.append(s[i])\n",
    "                        mi = s[i]\n",
    "                        s[i] = ''\n",
    "                        n -= 1\n",
    "            ma = ''\n",
    "            for i in range(len(s)-1,-1,-1):\n",
    "                if s[i] == '':\n",
    "                    continue\n",
    "                if not ma:\n",
    "                    ma = s[i]\n",
    "                    res.append(s[i])\n",
    "                    s[i] = ''\n",
    "                    n -= 1\n",
    "                else:\n",
    "                    if ma != s[i]:\n",
    "                        res.append(s[i])\n",
    "                        ma = s[i]\n",
    "                        s[i] = ''\n",
    "                        n -= 1\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        str_counter = collections.Counter(s)\n",
    "        result = []\n",
    "        flag = False\n",
    "        while str_counter:\n",
    "            keys = list(str_counter.keys())\n",
    "            keys.sort(reverse=flag)\n",
    "            flag = not flag\n",
    "            result.append(''.join(keys))\n",
    "            str_counter -= collections.Counter(keys)\n",
    "        return ''.join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        string = ''\n",
    "        counter = dict(Counter(sorted(s, key=lambda x: x)))\n",
    "        keys = counter.keys()\n",
    "        while True:\n",
    "            if not list(filter(lambda x: x > 0, counter.values())):\n",
    "                break\n",
    "            for key in keys:\n",
    "                if counter[key]:\n",
    "                    string += key\n",
    "                    counter[key] -= 1\n",
    "            for key in list(keys)[::-1]:\n",
    "                if counter[key]:\n",
    "                    string += key\n",
    "                    counter[key] -= 1\n",
    "\n",
    "        return string\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        res=''\n",
    "        cnt=[0 for i in range(26)]\n",
    "        for i in s:\n",
    "            cnt[ord(i)-ord('a')]+=1\n",
    "\n",
    "        while len(res)<len(s):\n",
    "            for i in range(26):\n",
    "                if cnt[i]:\n",
    "                    res+=chr(i+ord('a'))\n",
    "                    cnt[i]-=1\n",
    "            for i in range(25,-1,-1):\n",
    "                if cnt[i]:\n",
    "                    res+=chr(i+ord('a'))\n",
    "                    cnt[i]-=1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        str_counter = collections.Counter(s)\n",
    "        result = []\n",
    "        flag = False\n",
    "        while str_counter:\n",
    "            keys = list(str_counter.keys())\n",
    "            keys.sort(reverse=flag)\n",
    "            flag = not flag\n",
    "            result.append(''.join(keys))\n",
    "            str_counter -= collections.Counter(keys)\n",
    "        return ''.join(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        chrs = [0] * 26\n",
    "        for c in s:\n",
    "            chrs[ord(c)-ord('a')] += 1\n",
    "        ans = []\n",
    "        while len(ans) < len(s):\n",
    "            for i in range(26):\n",
    "                if chrs[i]:\n",
    "                    ans.append(chr(i + ord('a')))\n",
    "                    chrs[i] -= 1\n",
    "            for i in range(25, -1, -1):\n",
    "                if chrs[i]:\n",
    "                    ans.append(chr(i + ord('a')))\n",
    "                    chrs[i] -= 1\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        count = [0]*26\n",
    "        for ch in set(s):\n",
    "            count[ord(ch)-ord('a')] = s.count(ch)\n",
    "        res = \"\"\n",
    "        while len(res)<len(s):\n",
    "            for i in range(26):\n",
    "                if count[i]:\n",
    "                    res += chr(ord('a')+i)\n",
    "                    count[i] -= 1\n",
    "            for i in range(25,-1,-1):\n",
    "                if count[i]:\n",
    "                    res += chr(ord('a')+i)\n",
    "                    count[i] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        str_counter=collections.Counter(s)\n",
    "        result=[]\n",
    "        flag=False\n",
    "        while str_counter:\n",
    "            keys=list(str_counter.keys())\n",
    "            keys.sort(reverse=flag)\n",
    "            flag=not flag\n",
    "            result.append(''.join(keys))\n",
    "            str_counter-=collections.Counter(keys)\n",
    "        return ''.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        res = []\n",
    "        flag = False\n",
    "        s = collections.Counter(s)\n",
    "        while s:\n",
    "            param = list(s)\n",
    "            param.sort(reverse=flag)\n",
    "            flag = not flag\n",
    "            res.append(\"\".join(param))\n",
    "            s = s-collections.Counter(param)\n",
    "        \n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        d = Counter(s)\n",
    "        l = list(d.keys())\n",
    "        \n",
    "        res = []\n",
    "        t = False\n",
    "        while len(l):\n",
    "            l.sort(reverse = t)\n",
    "            tmp = l.copy()\n",
    "            # print(d)\n",
    "            for i in l:\n",
    "                res.append(i)\n",
    "                d[i]-=1\n",
    "                if d[i]==0:\n",
    "                    tmp.remove(i)\n",
    "                    # print(tmp,l)\n",
    "            \n",
    "            l = tmp    \n",
    "            t = not t    \n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "    \n",
    "        # 创建一个26个字母的桶\n",
    "        num = [0] * 26\n",
    "        for ch in s:\n",
    "            num[ord(ch) - ord('a')] += 1\n",
    "        res = list()\n",
    "        while len(res) < len(s):\n",
    "            for i in range(26):\n",
    "                if num[i]:\n",
    "                    res.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "            for i in range(25, -1, -1):\n",
    "                if num[i]:\n",
    "                    res.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "\n",
    "        return \"\".join(res) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        string = ''\n",
    "        counter = dict(Counter(sorted(s, key=lambda x: x)))\n",
    "        keys = list(counter.keys())\n",
    "        values = counter.values()\n",
    "        while True:\n",
    "            res_values = list(filter(lambda x: x > 0, values))\n",
    "            if not res_values:\n",
    "                break\n",
    "            for key in keys:\n",
    "                if counter[key]:\n",
    "                    string += key\n",
    "                    counter[key] -= 1\n",
    "            for key in keys[::-1]:\n",
    "                if counter[key]:\n",
    "                    string += key\n",
    "                    counter[key] -= 1\n",
    "            # keys = list(filter(lambda x: counter[x] > 0, keys))\n",
    "        return string\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        num = [0]*26\n",
    "        for ch in s:\n",
    "            num[ord(ch)-ord('a')]+=1\n",
    "        ret = list()\n",
    "        while len(ret) < len(s):\n",
    "            for i in range(26):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i+ord('a')))\n",
    "                    num[i]-=1\n",
    "            for i in range(25,-1,-1):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i+ord('a')))\n",
    "                    num[i]-=1\n",
    "        return \"\".join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        num = [0] * 26\n",
    "        for ch in s:\n",
    "            num[ord(ch) - ord('a')] += 1\n",
    "        \n",
    "        ret = list()\n",
    "        while len(ret) < len(s):\n",
    "            for i in range(26):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "            for i in range(25, -1, -1):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "\n",
    "        return \"\".join(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        str_counter = collections.Counter(s)\n",
    "        result = []\n",
    "        flag = False\n",
    "        while str_counter:\n",
    "            keys = list(str_counter.keys())\n",
    "            keys.sort(reverse=flag)\n",
    "            flag = not flag\n",
    "            result.append(''.join(keys))\n",
    "            str_counter -= collections.Counter(keys)\n",
    "        return ''.join(result)\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        num = [0] * 26\n",
    "        for ch in s:\n",
    "            num[ord(ch) - ord('a')] += 1\n",
    "        \n",
    "        ret = list()\n",
    "        while len(ret) < len(s):\n",
    "            for i in range(26):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "            for i in range(25, -1, -1):\n",
    "                if num[i]:\n",
    "                    ret.append(chr(i + ord('a')))\n",
    "                    num[i] -= 1\n",
    "\n",
    "        return \"\".join(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        lst = sorted(cnt.keys())\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        while len(ans) < n:\n",
    "            for w in lst:\n",
    "                if cnt[w]:\n",
    "                    ans.append(w)\n",
    "                    cnt[w] -= 1\n",
    "            for w in lst[::-1]:\n",
    "                if cnt[w]:\n",
    "                    ans.append(w)\n",
    "                    cnt[w] -= 1\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        total = Counter(s)\n",
    "        res = ''\n",
    "        a = ''.join(sorted(set(s)))\n",
    "        a += a[::-1]\n",
    "        while total:\n",
    "            for i in a:\n",
    "                if i in total:\n",
    "                    res += i\n",
    "                    total -= Counter(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        # 统计元素次数集合中字典\n",
    "        str_counter = collections.Counter(s)\n",
    "        result = []\n",
    "        flag = False\n",
    "        while str_counter:\n",
    "            # 将统计结果字母（建）转为列表\n",
    "            keys = list(str_counter.keys())\n",
    "            # 排序 先正后反\n",
    "            keys.sort(reverse=flag)\n",
    "            flag = not flag\n",
    "            # join以指定字符分割后面字符串\n",
    "            result.append(''.join(keys))\n",
    "            str_counter -= collections.Counter(keys)\n",
    "        return ''.join(result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        res = \"\"\n",
    "        while len(s) != 0 :\n",
    "            i = s.find(min(s))\n",
    "            res = res + s[i]\n",
    "            s = s[:i] + s[i+1:]\n",
    "            temp = s\n",
    "            # 找最小\n",
    "            while temp != \"\" :\n",
    "                i = s.find(min(temp))\n",
    "                j = temp.find(min(temp))\n",
    "                if s[i] > res[-1] :\n",
    "                    res = res + s[i]\n",
    "                    s = s[:i] + s[i+1:]\n",
    "                    temp = temp[:j] + temp[j+1:]\n",
    "                else:\n",
    "                    temp = temp[:j] + temp[j+1:]\n",
    "            if s != \"\": \n",
    "                i = s.find(max(s))\n",
    "                res = res + s[i]\n",
    "                s = s[:i] + s[i+1:]\n",
    "                temp = s\n",
    "                # 找最大\n",
    "                while temp != \"\" :\n",
    "                    i = s.find(max(temp))\n",
    "                    j = temp.find(max(temp))\n",
    "                    if s[i] < res[-1] :\n",
    "                        res = res + s[i]\n",
    "                        s = s[:i] + s[i+1:]\n",
    "                        temp = temp[:j] + temp[j+1:]\n",
    "                    else: \n",
    "                        temp = temp[:j] + temp[j+1:]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        ####使用数组存储字符出现的次数，然后模拟\n",
    "        tmp = [0] * 26\n",
    "        for i in s:\n",
    "            tmp[ord(i) - ord('a')] += 1\n",
    "        res = \"\"\n",
    "        n = len(s)\n",
    "        while len(res) < n:\n",
    "            for i in range(26):\n",
    "                if tmp[i] > 0:\n",
    "                    res += chr(i + ord('a'))\n",
    "                    if len(res) == n:\n",
    "                        return res\n",
    "                    tmp[i] -= 1\n",
    "            for i in range(25, -1, -1):\n",
    "                if tmp[i] > 0:\n",
    "                    res += chr(i + ord('a'))\n",
    "                    if len(res) == n:\n",
    "                        return res\n",
    "                    tmp[i] -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        remain=len(s)\n",
    "        counts=Counter(s)\n",
    "        chars=[]\n",
    "        for c in string.ascii_lowercase:\n",
    "            if c in counts:\n",
    "                chars.append(c)\n",
    "        is_order=True\n",
    "        cur=0\n",
    "        result=''\n",
    "        while remain>0:\n",
    "            if is_order:\n",
    "                c=chars[cur]\n",
    "            else:\n",
    "                c=chars[-1-cur]\n",
    "            if counts[c]>0:\n",
    "                result+=c\n",
    "                counts[c]-=1\n",
    "                remain-=1\n",
    "            cur+=1\n",
    "            if cur==len(chars):\n",
    "                cur=0\n",
    "                is_order=not is_order\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        s=list(s)\n",
    "        c=Counter(s)\n",
    "        ans=''\n",
    "        while c.total()>0:\n",
    "            for key,value in sorted(c.items(),key=lambda x:x[0]):\n",
    "                if value>0:\n",
    "                    ans+=key\n",
    "                    c[key]-=1\n",
    "            for key,value in sorted(c.items(),key=lambda x:x[0],reverse=True):\n",
    "                if value>0:\n",
    "                    ans+=key\n",
    "                    c[key]-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        #字典，key 从 a-z,value初始 0\n",
    "        strs=[0]*26\n",
    "        for c in s:\n",
    "            strs[ord(c)-ord('a')]+=1\n",
    "        print(strs)\n",
    "        res=\"\"\n",
    "        n=len(s)\n",
    "        while len(res)!=n:\n",
    "            # 第一轮，从小到大找字符\n",
    "            # 把索引转成字符，加到 res 后面\n",
    "            for i in range(26):\n",
    "                if strs[i]:\n",
    "                    ch=chr(i+97)\n",
    "                    res+=ch\n",
    "                    strs[i]-=1\n",
    "            # print(res)\n",
    "            # 从大到小找字符\n",
    "            for i in range(25,-1,-1):\n",
    "                if strs[i]:\n",
    "                    ch=chr(i+97)\n",
    "                    res+=ch\n",
    "                    strs[i]-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        s_list = list(s)\n",
    "        s_set = sorted(set(s_list))\n",
    "        res_str = []\n",
    "        i, s_len, num = 0, len(s_list), 0\n",
    "        while i < s_len:\n",
    "            index_list = []\n",
    "            for k in s_set:\n",
    "                if k in s_list:\n",
    "                    index_list.append(k)\n",
    "                    s_list.remove(k)\n",
    "                    i += 1\n",
    "            if num % 2 != 0:\n",
    "                index_list.reverse()\n",
    "            res_str += index_list\n",
    "            num += 1\n",
    "        return \"\".join(res_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        res = ''\n",
    "        sorted_s = sorted(s)\n",
    "        # print(sorted_s)\n",
    "\n",
    "        s_hashmap = Counter(sorted_s)\n",
    "        # print(s_hashmap)\n",
    "\n",
    "        checker = True\n",
    "        while checker:\n",
    "            for key in s_hashmap.keys():\n",
    "                if s_hashmap[key] <= 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    res += key\n",
    "                    s_hashmap[key] -= 1\n",
    "            \n",
    "            reverse_keys = ''\n",
    "            for key in s_hashmap.keys():\n",
    "                if s_hashmap[key] <= 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    reverse_keys += key\n",
    "                    s_hashmap[key] -= 1\n",
    "            res += reverse_keys[::-1]\n",
    "\n",
    "            checker = False\n",
    "            for key in s_hashmap.keys():\n",
    "                if s_hashmap[key] > 0:\n",
    "                    checker = True\n",
    "                    break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        string = ''\n",
    "        counter = dict(Counter(sorted(s, key=lambda x: x)))\n",
    "        keys = list(counter.keys())\n",
    "        values = counter.values()\n",
    "        while True:\n",
    "            res_values = list(filter(lambda x: x > 0, values))\n",
    "            if not res_values:\n",
    "                break\n",
    "            for key in keys:\n",
    "                if counter[key]:\n",
    "                    string += key\n",
    "                    counter[key] -= 1\n",
    "            for key in keys[::-1]:\n",
    "                if counter[key]:\n",
    "                    string += key\n",
    "                    counter[key] -= 1\n",
    "            # keys = list(filter(lambda x: counter[x] > 0, keys))\n",
    "        return string\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortString(self, s: str) -> str:\n",
    "        s=list(s)\n",
    "        s.sort()\n",
    "        ans = []\n",
    "        stack = []\n",
    "        ans.append(s[0])\n",
    "        n = len(s)\n",
    "        #print(s,ans)\n",
    "        for i in range(1,n):\n",
    "            if s[i] > ans[-1]:\n",
    "                ans.append(s[i])\n",
    "            else:\n",
    "                stack.append(s[i])\n",
    "            #print(stack,ans)\n",
    "        reverse = 1\n",
    "        while stack:\n",
    "            tmp = []\n",
    "            n = len(stack)\n",
    "            ans.append(stack[-1])\n",
    "            for i in range(n-2,-1,-1):\n",
    "                if reverse:\n",
    "                    if stack[i] < ans[-1]:\n",
    "                        ans.append(stack[i])\n",
    "                    else:\n",
    "                        tmp.append(stack[i])\n",
    "                else:\n",
    "                    if stack[i] > ans[-1]:\n",
    "                        ans.append(stack[i])\n",
    "                    else:\n",
    "                        tmp.append(stack[i])\n",
    "            stack = tmp\n",
    "            if reverse == 1:\n",
    "                reverse = 0\n",
    "            else:\n",
    "                reverse = 1\n",
    "        return ''.join(ans)\n",
    "        \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
